package _11_整理题目._7_查找排序._1_排序算法;

import org.junit.Test;

import java.util.Arrays;


/**
 * 平均时间复杂度是 O(n^2)
 * 平均空间复杂度是 O(1)
 *
 * 思路：
 *      将第一个元素看做有序，后面的序列看做无序
 *      遍历第二个到最后一个元素
 *          如果比前面的小，则依次插入到前面
 */
public class _04_插入排序 {
    
    public void insertionSort(int[] nums) {
        if (nums==null || nums.length==0) return;
        int n = nums.length;
        for (int i = 1; i < n; i++) {
            int cur = nums[i];

            int j = i;
            while (j > 0 && cur < nums[j-1]) {
                nums[j] = nums[j-1];
                j--;
            }

            if (j != i) {
                nums[j] = cur;
            }
        }
    }

    @Test
    public void main() {
        int[] ints = {1,4,2,6,7,3};
        insertionSort(ints);
        System.out.println(Arrays.toString(ints));
    }
}
